package com.sx.sx1.lintcode.day717;

public class LC751 {

    static class Solution {
        /**
         * @param a: The prices [i]
         * @param k:
         * @return: The ans array
         */
        public int[] business(int[] a, int k) {
            int n = a.length;
            SegmentNode root = buildTree(a,0,a.length-1);
            int[] ans = new int[n];
            for (int i = 0; i <n ; i++) {
                int start = Math.max(i-k,0);
                int end = Math.min(i+k,n-1);
                ans[i] = a[i]- query(root,start,end);
            }
            return ans;
        }


        public SegmentNode buildTree(int[] arr,int start,int end){
            if(start == end){
                return new SegmentNode(start,end,arr[start]);
            }

            SegmentNode root = new SegmentNode(start,end,Integer.MAX_VALUE);
            int m = start+((end-start) >> 1);
            root.left = buildTree(arr,start,m);
            root.right = buildTree(arr,m+1,end);
            root.data = Math.min(root.left.data,root.right.data);
            return root;
        }


        public int query(SegmentNode root,int start,int end){
            if(start <= root.start && end >= root.end){
                return root.data;
            }

            int m = root.start+((root.end-root.start)>>1);
            int left =Integer.MAX_VALUE;
            int right = Integer.MAX_VALUE;
            if(m >=start) {
                left= query(root.left,start,Math.min(m,end));
            }

            if(m<end){
                right = query(root.right,m>=start? m+1:start,end);
            }

            return Math.min(left,right);
        }
        static class SegmentNode{
            public int start,end,data; //data:最小值
            public SegmentNode left,right;
            public SegmentNode(int s,int e,int d){
                start = s;
                end =e;
                data =d;
            }
        }

    }


    public static void main(String[] args) {
        Solution obj = new Solution();
        int[] arr = obj.business(new int[]{1,3,2,1,5},2);
        for (int i : arr) {
            System.out.print(i+" ");
        }
    }

    static class Solution1 {
        /**
         * @param a: The prices [i]
         * @param k:
         * @return: The ans array
         */
        public int[] business(int[] a, int k) {
            int n = a.length;
            int[] ans = new int[n];
            SegmentNode root = build(0, n - 1, a);
            for (int i = 0; i < n; i++) {
                int left = i - k, right = i + k;
                if (left < 0) left = 0;
                if (right > n - 1) right = n - 1;
                ans[i] = a[i] - query(root, left, right);
            }
            return ans;
        }

        static class SegmentNode { //线段树节点
            int start, end, min;
            SegmentNode left, right;

            public SegmentNode(int s, int e) {
                start = s;
                end = e;
            }
        }

        //创建线段树
        public static SegmentNode build(int start, int end, int[] arr) {
            if (start > end) return null;
            if (start == end) {
                SegmentNode nn = new SegmentNode(start, end);
                nn.min = arr[start];
                return nn;
            }

            SegmentNode root = new SegmentNode(start, end);
            root.min = Integer.MAX_VALUE;
            int mid = (start + end) / 2;
            root.left = build(start, mid, arr);
            root.right = build(mid + 1, end, arr);

            if (root.left != null)
                root.min = Math.min(root.min, root.left.min);

            if (root.right != null)
                root.min = Math.min(root.min, root.right.min);

            return root;
        }

        //查询
        public static int query(SegmentNode root, int start, int end) {
            if (root.start == start && root.end == end) {
                return root.min;
            }

            int mid = (root.start + root.end) / 2;
            int left = Integer.MAX_VALUE;
            int right = Integer.MAX_VALUE;
            if (mid >= start) {
                if (mid < end) {
                    left = query(root.left, start, mid);
                } else {
                    left = query(root.left, start, end);
                }
            }

            if (mid < end) {
                if (mid >= start) {
                    right = query(root.right, mid + 1, end);
                } else {
                    right = query(root.right, start, end);
                }
            }

            return Math.min(left, right);
        }
    }


}


/*
LintCode-Logo
搜索题目、标签、题集
中文
avatar
您有186条未读消息，请及时查看
751 · 约翰的生意
算法
中等
通过率
50%

题目
题解14
笔记
讨论27
排名
记录
描述
在一条数轴上，有n个城市，编号从0 ~ n – 1 , 约翰打算在这n个城市做点生意，他对Armani的一批货物感兴趣，每个城市对于这批货物都有一个价格prices[i]。
对于城市x,约翰可从城市编号为[x - k, x + k]购买货物，然后卖到城市x,问约翰在每个城市最多能赚到多少钱？


最短时间刷“透”算法面试：《66页算法宝典》.pdf

微信添加【jiuzhangfeifei】备注【66】领取


prices.length 范围为[2, 100000], k <= 100000。

样例
样例1

输入: prices = [1, 3, 2, 1, 5] 和 k = 2
输出: [0, 2, 1, 0, 4]
解释:
i = 0，约翰可去的城市有0~2因为1、2号城市的价格比0号城市的价格高，所以赚不了钱，即 ans[0] = 0。
i = 1，可去的城市有0~3，可以从0号或者3号城市购买货物赚取的差价最大，即ans[1] = 2。
i = 2，可去的城市有0~4，显然从3号城市购买货物赚取的差价最大，即ans[2] = 1。
i = 3，可去的城市有1~4，没有其他城市的价格比3号城市价格低，所以赚不了钱，ans[3] = 0。
i = 4，可去的城市有2~4，从3号城市购买货物赚取的差价最大，即ans[4] = 4。
样例2

输入: prices = [1, 1, 1, 1, 1] 和 k = 1
输出: [0, 0, 0, 0, 0]
解释:
所有城市价格都一样，所以不能赚到钱，即所有的ans都为0。
标签
相关题目

201
线段树的构造
中等

202
线段树的查询
中等

205
区间最小数
中等
推荐课程

0基础入门数据分析
进阶大厂刚需高薪人才，熟练掌握SQL、Python、Tableau、A/Btest等实用技能工具，配套100+数据题夯实基础
已开启智能提示
发起考试
30 分 00 秒
12345678910
public class Solution {
    /**
     * @param a: The prices [i]
     * @param k:
     * @return: The ans array

public int[] business(int[] a, int k) {
    //
}
}
控制台
        历史提交

 */
